package algorithm.t202112;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/12/6 10:57
 * @description :5道
 * 今天是被图折磨的一天，太难了，邻接表，弗洛伊德等等，太多东西了，之前图的题也做的太少，看来得花时间好好把图学习一下了（估计这过程很痛苦），这几天准备看看房
 子，周末去锦业路看看租房，要去实习了，公司那边说可以22号到岗，但不知道学校这边放不放人，唉，算法还是太难了啊（题做的太少），看样子做题要到700+才能去冲击
 大厂了，现在还不到350，唉，冲，奋斗！
 persevere to last
 2021.12.6
 李红磊
 2021年12月6日20:45:48
 */
public class t20211206 {

    //1816.截断句子
    public String truncateSentence(String s, int k) {
        return null;
    }

    //701.二叉搜索树中的插入操作
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        int r_val = root.val;
        if (val > r_val) {
            if (root.right == null) {
                root.right = new TreeNode(val);
                return root;
            }
            insertIntoBST(root.right, val);
        } else {
            if (root.left == null) {
                root.left = new TreeNode(val);
                return root;
            }
            insertIntoBST(root.left, val);
        }

        return root;
    }

    //931.下降路径最小和
    public int minFallingPathSum(int[][] matrix) {
        return 0;
    }

    //1042.不邻接植花
    public int[] gardenNoAdj(int n, int[][] paths) {
        List<List<Integer>> graph = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < paths.length; i++) {
            graph.get(paths[i][0] - 1).add(paths[i][1] - 1);
            graph.get(paths[i][1] - 1).add(paths[i][0] - 1);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            Set<Integer> color = new HashSet() {{
                add(1);
                add(2);
                add(3);
                add(4);
            }};
            for (int j = 0; j < graph.get(i).size(); j++) {
                color.remove(ans[graph.get(i).get(j)]);
            }
            ans[i] = color.iterator().next();
        }
        return ans;
    }

    //787.K站中转内最便宜的航班
    int INF = 1000007;
    int[][] memory;
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        memory = new int[n][k + 2];

        int ans = dfs(flights, src, dst, k + 1);
        return ans == INF ? -1 : ans;
    }
    private int dfs(int[][] flights, int cur, int dst, int k) {
        if (k < 0) return INF;
        if (cur == dst) return 0;

        if (memory[cur][k] != 0) return memory[cur][k];

        int min = INF;
        for (int[] item : flights) {
            if (item[0] == cur) {
                min = Math.min(min, dfs(flights, item[1], dst, k - 1) + item[2]);
            }
        }
        memory[cur][k] = min;
        return min;
    }


    public static void main(String[] args) {
        String s = "hello world";
        t20211206 t20211206 = new t20211206();
        HashSet<Integer> set = new HashSet() {{
            add(1);
            add(2);
            add(7);
            add(4);
        }};

        Iterator<Integer> iterator = set.iterator();

        while (iterator.hasNext()) {
            System.out.println(iterator.next());

        }

    }

}
